public class test {
    //leetcode 474.一和零
    class Solution {
        //(三维解法)
        public int findMaxForm(String[] strs, int m, int n) {
            // 1. 创建 dp 表
            int len = strs.length;
            //遍历第 i 个字符串时,0个数不超过 j,1个数不超过 k 的字符串个数.
            int[][][] dp = new int[len+1][m+1][n+1];
            // 2. 初始化

            // 3. 填表
            for(int i = 1;i <= len;i++){
                int[] nums = get01(strs[i - 1]);
                int num1 = nums[0];//0个数
                int num2 = nums[1];//1个数
                for(int j = 0;j <= m;j++){
                    for(int k = 0;k <= n;k++){
                        dp[i][j][k] = dp[i-1][j][k];
                        if(j >= num1 && k >= num2){
                            dp[i][j][k] = Math.max(dp[i][j][k],dp[i-1][j-num1][k-num2] + 1);
                        }
                    }
                }
            }
            // 4. 返回值
            return dp[len][m][n];
        }
        //二维费用的 01背包 问题(二维解法)
        public int findMaxForm1(String[] strs, int m, int n) {
            // 1. 创建 dp 表
            //遍历到第 i 个字符串时,0个数不超过m 1个数不超过n的字符串个数.
            int len = strs.length;
            int[][] dp = new int[m+1][n+1];
            // 2. 初始化

            // 3. 填表
            for(int i = 0;i < len;i++){
                //获取当前字符串的 01 个数
                int[] num = get01(strs[i]);
                for(int j = m;j >= num[0];j--){
                    for(int k = n;k >= num[1];k--){
                        dp[j][k] = Math.max(dp[j][k],dp[j - num[0]][k - num[1]] + 1);
                    }
                }
            }
            // 4. 返回值
            return dp[m][n];
        }
        public int[] get01(String s){
            int[] arr = new int[2];
            int len = s.length();
            for(int i = 0;i < len;i++){
                if(s.charAt(i) == '0'){
                    arr[0]++;
                }else {
                    arr[1]++;
                }
            }
            return arr;
        }
    }
    //leetcode 279.完全平方数
    class Solution {
        public int numSquares(int n) {
            // 1. 创建 dp 表
            //代表正数为 i 时,返回和为 j 的完全平方数最少数量
            int[] dp = new int[n+1];
            // 2. 初始化
            for(int i = 1;i <= n;i++){
                dp[i] = i;
            }
            // 3. 填表
            for(int i = 1;i <= 100;i++){
                for(int j = 1;j <= n;j++){
                    int num = i * i;
                    if(j >= num){
                        dp[j] = Math.min(dp[j],dp[j - num] + 1);
                    }
                }
            }
            // 4. 返回值
            return dp[n];
        }
    }
}
